<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
      <title>GTL - Graph Template Library: ratio_cut_partition.h Source File</title>
      <link href="doxygen.css" rel="stylesheet" type="text/css">
  </head>
  <body>
    <p class="links">  
      <a href="../index.html">Home</a> |
      Documentation |
      <a href="../register.html">Download</a> |
      <a href="../platforms.html">Platforms</a> |
      <a href="../refer.html">Projects</a> |      
      <a href="../lists.html">Mailing Lists</a> |
      <a href="../history.html">Version History</a>
    </p>

<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
  <ul>
    <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    <li><a href="classes.html"><span>Classes</span></a></li>
    <li class="current"><a href="files.html"><span>Files</span></a></li>
    <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
  </ul>
</div>
<h1>ratio_cut_partition.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
<a name="l00002"></a>00002 <span class="comment">//</span>
<a name="l00003"></a>00003 <span class="comment">//      ratio_cut_partition.h</span>
<a name="l00004"></a>00004 <span class="comment">//</span>
<a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
<a name="l00006"></a>00006 <span class="comment">// $Id: ratio_cut_partition.h,v 1.8 2003/01/31 08:15:04 chris Exp $</span>
<a name="l00007"></a>00007 
<a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_RATIO_CUT_PARTITION_H</span>
<a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_RATIO_CUT_PARTITION_H</span>
<a name="l00010"></a>00010 <span class="preprocessor"></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
<a name="l00012"></a>00012 <span class="preprocessor">#include &lt;GTL/graph.h&gt;</span>
<a name="l00013"></a>00013 <span class="preprocessor">#include &lt;GTL/node_map.h&gt;</span>
<a name="l00014"></a>00014 <span class="preprocessor">#include &lt;GTL/edge_map.h&gt;</span>
<a name="l00015"></a>00015 <span class="preprocessor">#include &lt;GTL/algorithm.h&gt;</span>
<a name="l00016"></a>00016 
<a name="l00017"></a>00017 __GTL_BEGIN_NAMESPACE
<a name="l00018"></a>00018 
<a name="l00019"></a>00019 
<a name="l00031"></a><a class="code" href="a00025.html">00031</a> <span class="keyword">class </span>GTL_EXTERN <a class="code" href="a00025.html" title="Heuristic graph bi-partitioning algorithm (Wei-Cheng).">ratio_cut_partition</a> : <span class="keyword">public</span> <a class="code" href="a00001.html" title="Abstract baseclass for all algoritm-classes.">algorithm</a>
<a name="l00032"></a>00032 {
<a name="l00033"></a>00033 <span class="keyword">public</span>:
<a name="l00040"></a><a class="code" href="a00025.html#ce53442bd0c1e21fbf00858ec6f6b456">00040</a>     <span class="keyword">typedef</span> <span class="keywordtype">int</span> side_type;
<a name="l00041"></a>00041 
<a name="l00047"></a><a class="code" href="a00025.html#81bfe2382ea876b98112143593612cb4">00047</a>     <span class="keyword">const</span> <span class="keyword">static</span> side_type A;
<a name="l00048"></a>00048 
<a name="l00054"></a><a class="code" href="a00025.html#df8f7eaaf11ff5461f3f4404010a05cb">00054</a>     <span class="keyword">const</span> <span class="keyword">static</span> side_type B;
<a name="l00055"></a>00055 
<a name="l00064"></a><a class="code" href="a00025.html#558dda40abda8ab03edb4605dbb81e36">00064</a>     <span class="keyword">typedef</span> <span class="keywordtype">short</span> <span class="keywordtype">int</span> fix_type;
<a name="l00065"></a>00065 
<a name="l00071"></a><a class="code" href="a00025.html#c964b04d22ceb3ea2d49780df72032f3">00071</a>     <span class="keyword">const</span> <span class="keyword">static</span> fix_type FIXA;
<a name="l00072"></a>00072 
<a name="l00078"></a><a class="code" href="a00025.html#31884bac5dce93e880836925a2cc71c9">00078</a>     <span class="keyword">const</span> <span class="keyword">static</span> fix_type FIXB;
<a name="l00079"></a>00079 
<a name="l00085"></a><a class="code" href="a00025.html#2a1522e3dc701ac6af359614a111a1df">00085</a>     <span class="keyword">const</span> <span class="keyword">static</span> fix_type UNFIXED;
<a name="l00086"></a>00086 
<a name="l00092"></a>00092     <a class="code" href="a00025.html" title="Heuristic graph bi-partitioning algorithm (Wei-Cheng).">ratio_cut_partition</a>();
<a name="l00093"></a>00093 
<a name="l00099"></a>00099     <span class="keyword">virtual</span> ~<a class="code" href="a00025.html" title="Heuristic graph bi-partitioning algorithm (Wei-Cheng).">ratio_cut_partition</a>();
<a name="l00100"></a>00100 
<a name="l00112"></a>00112     <span class="keywordtype">void</span> set_vars(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; node_weight,
<a name="l00113"></a>00113         <span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; edge_weight);
<a name="l00114"></a>00114 
<a name="l00128"></a>00128     <span class="keywordtype">void</span> set_vars(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; node_weight,
<a name="l00129"></a>00129         <span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; edge_weight, <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> source_node,
<a name="l00130"></a>00130         <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> target_node);
<a name="l00131"></a>00131 
<a name="l00150"></a>00150     <span class="keywordtype">void</span> set_vars(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; node_weight,
<a name="l00151"></a>00151         <span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; edge_weight, <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> source_node,
<a name="l00152"></a>00152         <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> target_node, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;side_type&gt;</a>&amp; init_side);
<a name="l00153"></a>00153                         
<a name="l00172"></a>00172     <span class="keywordtype">void</span> set_vars(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; node_weight,
<a name="l00173"></a>00173         <span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; edge_weight, <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> source_node,
<a name="l00174"></a>00174         <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> target_node, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;fix_type&gt;</a>&amp; fixed);
<a name="l00175"></a>00175 
<a name="l00199"></a>00199     <span class="keywordtype">void</span> set_vars(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a>&amp; node_weight,
<a name="l00200"></a>00200         <span class="keyword">const</span> <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a>&amp; edge_weight, <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> source_node,
<a name="l00201"></a>00201         <span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> target_node, <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;side_type&gt;</a>&amp; init_side,
<a name="l00202"></a>00202         <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;fix_type&gt;</a>&amp; fixed);
<a name="l00203"></a>00203 
<a name="l00213"></a>00213     <span class="keywordtype">void</span> store_cut_edges(<span class="keyword">const</span> <span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00214"></a>00214 
<a name="l00226"></a>00226     <span class="keywordtype">void</span> store_nodesAB(<span class="keyword">const</span> <span class="keywordtype">bool</span> <span class="keyword">set</span>);
<a name="l00227"></a>00227 
<a name="l00252"></a>00252     <span class="keyword">virtual</span> <span class="keywordtype">int</span> <a class="code" href="a00001.html#76361fb03ad1cf643affc51821e43bed" title="Checks whether all preconditions are satisfied.">check</a>(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00253"></a>00253 
<a name="l00264"></a>00264     <span class="keywordtype">int</span> <a class="code" href="a00001.html#734b189509a8d6b56b65f8ff772d43ca" title="Applies algorithm to graph g.">run</a>(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00265"></a>00265 
<a name="l00271"></a>00271     <span class="keywordtype">int</span> get_cutsize();
<a name="l00272"></a>00272                 
<a name="l00279"></a>00279     <span class="keywordtype">double</span> get_cutratio();
<a name="l00280"></a>00280                 
<a name="l00289"></a>00289     side_type get_side_of_node(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) <span class="keyword">const</span>;
<a name="l00290"></a>00290 
<a name="l00300"></a>00300     side_type operator [](<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; n) <span class="keyword">const</span>;
<a name="l00301"></a>00301                                 
<a name="l00309"></a>00309     <span class="keywordtype">int</span> get_weight_on_sideA(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G) <span class="keyword">const</span>;
<a name="l00310"></a>00310 
<a name="l00318"></a>00318     <span class="keywordtype">int</span> get_weight_on_sideB(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G) <span class="keyword">const</span>;
<a name="l00319"></a>00319 
<a name="l00323"></a><a class="code" href="a00025.html#5269af60e49810067411b085a1341adc">00323</a>     <span class="keyword">typedef</span> list&lt;edge&gt;::const_iterator cut_edges_iterator;
<a name="l00324"></a>00324 
<a name="l00333"></a>00333     cut_edges_iterator cut_edges_begin() <span class="keyword">const</span>;
<a name="l00334"></a>00334 
<a name="l00343"></a>00343     cut_edges_iterator cut_edges_end() <span class="keyword">const</span>;
<a name="l00344"></a>00344                 
<a name="l00348"></a><a class="code" href="a00025.html#4f667099b56ded1bfef8f1fb4d09f81c">00348</a>     <span class="keyword">typedef</span> list&lt;node&gt;::const_iterator nodes_of_one_side_iterator;
<a name="l00349"></a>00349 
<a name="l00357"></a>00357     nodes_of_one_side_iterator nodes_of_sideA_begin() <span class="keyword">const</span>;
<a name="l00358"></a>00358 
<a name="l00367"></a>00367     nodes_of_one_side_iterator nodes_of_sideA_end() <span class="keyword">const</span>;
<a name="l00368"></a>00368 
<a name="l00376"></a>00376     nodes_of_one_side_iterator nodes_of_sideB_begin() <span class="keyword">const</span>;
<a name="l00377"></a>00377 
<a name="l00386"></a>00386     nodes_of_one_side_iterator nodes_of_sideB_end() <span class="keyword">const</span>;
<a name="l00387"></a>00387 
<a name="l00394"></a>00394     <span class="keyword">virtual</span> <span class="keywordtype">void</span> <a class="code" href="a00001.html#21aba63d066ae7897de6ca7d8425c408" title="Resets algorithm.">reset</a>();
<a name="l00395"></a>00395 <span class="keyword">protected</span>:
<a name="l00399"></a>00399     <span class="keyword">enum</span> direction_type {LEFT_SHIFT = 2, RIGHT_SHIFT = 3};
<a name="l00400"></a>00400 
<a name="l00406"></a>00406     <span class="keywordtype">bool</span> enable_cut_edges_storing;
<a name="l00407"></a>00407                 
<a name="l00412"></a>00412     list&lt;edge&gt; cut_edges;
<a name="l00413"></a>00413 
<a name="l00419"></a>00419     <span class="keywordtype">bool</span> enable_nodesAB_storing;
<a name="l00420"></a>00420                 
<a name="l00425"></a>00425     list&lt;node&gt; nodesA;
<a name="l00426"></a>00426 
<a name="l00431"></a>00431     list&lt;node&gt; nodesB;
<a name="l00432"></a>00432 
<a name="l00437"></a>00437     <a class="code" href="a00020.html" title="A node in a graph.">node</a> source_node;
<a name="l00438"></a>00438 
<a name="l00443"></a>00443     <a class="code" href="a00020.html" title="A node in a graph.">node</a> target_node;
<a name="l00444"></a>00444 
<a name="l00451"></a>00451     <span class="keywordtype">bool</span> set_vars_executed;
<a name="l00452"></a>00452 
<a name="l00458"></a>00458     <span class="keywordtype">bool</span> provided_st;
<a name="l00459"></a>00459 
<a name="l00466"></a>00466     <span class="keywordtype">bool</span> provided_initial_part;
<a name="l00467"></a>00467 
<a name="l00473"></a>00473     <span class="keywordtype">bool</span> provided_fix;
<a name="l00474"></a>00474                 
<a name="l00479"></a>00479     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;fix_type&gt;</a> fixed;
<a name="l00480"></a>00480 
<a name="l00486"></a>00486     direction_type direction;
<a name="l00487"></a>00487 
<a name="l00493"></a>00493     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> node_weight;
<a name="l00494"></a>00494 
<a name="l00500"></a>00500     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a> edge_weight;
<a name="l00501"></a>00501 
<a name="l00507"></a>00507     <span class="keywordtype">int</span> max_edge_weight;
<a name="l00508"></a>00508 
<a name="l00514"></a>00514     <span class="keywordtype">int</span> node_weight_on_sideA;
<a name="l00515"></a>00515 
<a name="l00521"></a>00521     <span class="keywordtype">int</span> node_weight_on_sideB;
<a name="l00522"></a>00522                 
<a name="l00527"></a>00527     <span class="keywordtype">int</span> nodes_on_sideA;
<a name="l00528"></a>00528                 
<a name="l00533"></a>00533     <span class="keywordtype">int</span> nodes_on_sideB;
<a name="l00534"></a>00534                 
<a name="l00539"></a>00539     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;side_type&gt;</a> side;
<a name="l00540"></a>00540                 
<a name="l00545"></a>00545     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;list&lt;node&gt;::iterator</a>&gt; position_in_bucket;
<a name="l00546"></a>00546                 
<a name="l00551"></a>00551     <span class="keywordtype">int</span> max_vertex_degree;
<a name="l00552"></a>00552 
<a name="l00557"></a>00557     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a> aside;
<a name="l00558"></a>00558 
<a name="l00563"></a>00563     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;int&gt;</a> bside;
<a name="l00564"></a>00564 
<a name="l00570"></a>00570     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;list&lt;node&gt;</a> &gt; unlockedA;
<a name="l00571"></a>00571 
<a name="l00577"></a>00577     <a class="code" href="a00011.html" title="A specialized map with edges as keys.">edge_map&lt;list&lt;node&gt;</a> &gt; unlockedB;
<a name="l00578"></a>00578 
<a name="l00583"></a>00583     <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;int&gt;</a> gain_value;
<a name="l00584"></a>00584 
<a name="l00589"></a>00589     <span class="keywordtype">bool</span> bucketA_empty;
<a name="l00590"></a>00590 
<a name="l00595"></a>00595     <span class="keywordtype">bool</span> bucketB_empty;
<a name="l00596"></a>00596 
<a name="l00602"></a>00602     <span class="keywordtype">int</span> max_gainA;
<a name="l00603"></a>00603 
<a name="l00609"></a>00609     <span class="keywordtype">int</span> max_gainB;
<a name="l00610"></a>00610                 
<a name="l00617"></a>00617     vector&lt;list&lt;node&gt; &gt; bucketA;
<a name="l00618"></a>00618 
<a name="l00625"></a>00625     vector&lt;list&lt;node&gt; &gt; bucketB;
<a name="l00626"></a>00626 
<a name="l00632"></a>00632     <span class="keywordtype">int</span> cur_cutsize;
<a name="l00633"></a>00633 
<a name="l00638"></a>00638     <span class="keywordtype">double</span> cur_cutratio;
<a name="l00639"></a>00639 
<a name="l00645"></a>00645     <span class="keywordtype">void</span> divide_up(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00646"></a>00646 
<a name="l00653"></a>00653     <span class="keywordtype">void</span> make_connected(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, list&lt;edge&gt;&amp; artificial_edges);
<a name="l00654"></a>00654                 
<a name="l00660"></a>00660     <span class="keywordtype">void</span> restore(<a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, list&lt;edge&gt;&amp; artificial_edges);
<a name="l00661"></a>00661                 
<a name="l00666"></a>00666     <span class="keywordtype">void</span> initialization(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00667"></a>00667 
<a name="l00672"></a>00672     <span class="keywordtype">void</span> init_data_structure(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00673"></a>00673 
<a name="l00679"></a>00679     <span class="keywordtype">void</span> init_filling_buckets(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00680"></a>00680 
<a name="l00686"></a>00686     <span class="keywordtype">int</span> inital_gain_of_node_on_sideA(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node);
<a name="l00687"></a>00687 
<a name="l00693"></a>00693     <span class="keywordtype">int</span> inital_gain_of_node_on_sideB(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node);
<a name="l00694"></a>00694 
<a name="l00699"></a>00699     <span class="keywordtype">void</span> init_variables(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00700"></a>00700                 
<a name="l00705"></a>00705     <span class="keywordtype">void</span> compute_max_vertex_degree(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00706"></a>00706 
<a name="l00711"></a>00711     <span class="keywordtype">void</span> determine_source_node(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00712"></a>00712 
<a name="l00717"></a>00717     <span class="keywordtype">void</span> compute_target_node(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00718"></a>00718 
<a name="l00724"></a>00724     <span class="keywordtype">void</span> right_shift_op(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00725"></a>00725 
<a name="l00731"></a>00731     <span class="keywordtype">void</span> left_shift_op(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00732"></a>00732 
<a name="l00740"></a>00740     <span class="keywordtype">bool</span> move_vertex_A2B(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; moved_node);
<a name="l00741"></a>00741 
<a name="l00748"></a>00748     <span class="keywordtype">bool</span> move_vertex_B2A(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; moved_node);
<a name="l00749"></a>00749 
<a name="l00754"></a>00754     <a class="code" href="a00020.html" title="A node in a graph.">node</a> compute_highest_ratio_node(list&lt;node&gt; node_list);
<a name="l00755"></a>00755 
<a name="l00763"></a>00763     <span class="keywordtype">double</span> cutratio();
<a name="l00764"></a>00764                                 
<a name="l00771"></a>00771     <span class="keywordtype">double</span> ratio_of_node_A2B(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node);
<a name="l00772"></a>00772 
<a name="l00779"></a>00779     <span class="keywordtype">double</span> ratio_of_node_B2A(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node);
<a name="l00780"></a>00780                 
<a name="l00786"></a>00786     <span class="keyword">inline</span> <span class="keywordtype">int</span> range_up(<span class="keyword">const</span> <span class="keywordtype">int</span> gain_value) <span class="keyword">const</span>;
<a name="l00787"></a>00787 
<a name="l00793"></a>00793     <span class="keyword">inline</span> <span class="keywordtype">int</span> range_down(<span class="keyword">const</span> <span class="keywordtype">int</span> index) <span class="keyword">const</span>;
<a name="l00794"></a>00794 
<a name="l00800"></a>00800     <span class="keywordtype">void</span> update_data_structure_A2B(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node,
<a name="l00801"></a>00801         <span class="keyword">const</span> <span class="keywordtype">bool</span> init_mode);
<a name="l00802"></a>00802                 
<a name="l00808"></a>00808     <span class="keywordtype">void</span> update_data_structure_B2A(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node,
<a name="l00809"></a>00809         <span class="keyword">const</span> <span class="keywordtype">bool</span> init_mode);
<a name="l00810"></a>00810                 
<a name="l00816"></a>00816     <span class="keywordtype">void</span> update_bucketA(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node, <span class="keyword">const</span> <span class="keywordtype">int</span> old_gain,
<a name="l00817"></a>00817         <span class="keyword">const</span> <span class="keywordtype">int</span> new_gain, <span class="keyword">const</span> <span class="keywordtype">bool</span> init_mode);
<a name="l00818"></a>00818 
<a name="l00824"></a>00824     <span class="keywordtype">void</span> update_bucketB(<span class="keyword">const</span> <a class="code" href="a00020.html" title="A node in a graph.">node</a> cur_node, <span class="keyword">const</span> <span class="keywordtype">int</span> old_gain,
<a name="l00825"></a>00825         <span class="keyword">const</span> <span class="keywordtype">int</span> new_gain, <span class="keyword">const</span> <span class="keywordtype">bool</span> init_mode);
<a name="l00826"></a>00826                 
<a name="l00832"></a>00832     <span class="keywordtype">void</span> update_max_gain(<span class="keyword">const</span> side_type side);
<a name="l00833"></a>00833 
<a name="l00838"></a>00838     <span class="keywordtype">void</span> clean_step(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00839"></a>00839 
<a name="l00844"></a>00844     <span class="keywordtype">void</span> copy_side_node_map(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;side_type&gt;</a>&amp; dest,
<a name="l00845"></a>00845         <span class="keyword">const</span> <a class="code" href="a00021.html" title="A specialized map with nodes as keys.">node_map&lt;side_type&gt;</a> source) <span class="keyword">const</span>;
<a name="l00846"></a>00846                         
<a name="l00851"></a>00851     <span class="keywordtype">void</span> iterative_shifting(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00852"></a>00852 
<a name="l00857"></a>00857     <span class="keywordtype">void</span> group_swapping(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00858"></a>00858 
<a name="l00865"></a>00865     <span class="keywordtype">bool</span> move_manager(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00866"></a>00866 
<a name="l00873"></a>00873     <span class="keywordtype">bool</span> move_vertex(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G, <a class="code" href="a00020.html" title="A node in a graph.">node</a>&amp; moved_node);
<a name="l00874"></a>00874 
<a name="l00879"></a>00879     <span class="keywordtype">void</span> compute_cut_edges(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00880"></a>00880 
<a name="l00885"></a>00885     <span class="keywordtype">void</span> compute_nodesAB(<span class="keyword">const</span> <a class="code" href="a00014.html" title="A directed or undirected graph.">graph</a>&amp; G);
<a name="l00886"></a>00886 <span class="keyword">private</span>:
<a name="l00887"></a>00887 <span class="preprocessor">#ifdef _DEBUG</span>
<a name="l00888"></a>00888 <span class="preprocessor"></span>
<a name="l00892"></a>00892     <span class="keywordtype">void</span> print_bucketA();
<a name="l00893"></a>00893 
<a name="l00898"></a>00898     <span class="keywordtype">void</span> print_bucketB();
<a name="l00899"></a>00899 <span class="preprocessor">#endif  // _DEBUG</span>
<a name="l00900"></a>00900 <span class="preprocessor"></span>};
<a name="l00901"></a>00901 
<a name="l00902"></a>00902 __GTL_END_NAMESPACE
<a name="l00903"></a>00903 
<a name="l00904"></a>00904 <span class="preprocessor">#endif // GTL_RATIO_CUT_PARTITION_H</span>
<a name="l00905"></a>00905 <span class="preprocessor"></span>
<a name="l00906"></a>00906 <span class="comment">//--------------------------------------------------------------------------</span>
<a name="l00907"></a>00907 <span class="comment">//   end of file</span>
<a name="l00908"></a>00908 <span class="comment">//--------------------------------------------------------------------------</span>
</pre></div>    <p class="links">
      <a href="http://www.uni-passau.de/">University of Passau</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/">FMI</a>
      &nbsp;-&nbsp;
      <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
	Computer Science</a>
    </p>
  <div class="copyright">
      Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
  </div>
</body>
</html>
